#!/usr/bin/python3
#! -*- coding:utf-8 -*-

import random
from caltime import runtime


def merge(ls, low, mid, high):
    i = low
    j = mid + 1
    tmp = []
    while i <= mid and j <= high:  # 保证 mid 的左侧和右侧都至少有一个元素
        if ls[i] < ls[j]:  # 如果左侧数小
            # 把左侧的数存入临时列表中
            tmp.append(ls[i])
            # i向右走一位
            i += 1
        else:  # 如果右侧的数小
            # 把右侧的数存入临时列表中
            tmp.append(ls[j])
            # j向右走一位
            j += 1
    # 当完成归并后，可能mid左侧剩一些元素，也可能mid右侧剩一些元素。
    # 以上两种情况只会出现一种
    # 也要把他们写进临时列表中
    while i <= mid:
        tmp.append(ls[i])
        i += 1
    while j <= high:
        tmp.append(ls[j])
        j += 1
    # 把临时列表tmp写回原列表中
    ls[low:high + 1] = tmp


def _merge_sort(ls, low, high):
    if low < high:
        mid = (low + high) // 2
        _merge_sort(ls, low, mid)
        _merge_sort(ls, mid + 1, high)
        merge(ls, low, mid, high)


@runtime
def merge_sort(ls):
    _merge_sort(ls, 0, len(ls) - 1)


lst = [random.randint(-1000, 1000) for _ in range(1000)]
# print('原列表>>>', lst)
merge_sort(lst)
# print('排序后的列表>>>', lst)
